/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓␈↓↓This␈α∪draft␈α∪gives␈α∪insufficient␈α∪mention␈α∪to␈α∪many␈α∪people␈α∪who␈α∪helped␈α∪implement␈α∪LISP␈α∀and␈α∪who
␈↓ ↓H␈↓↓contributed ideas.  Suggestions for improvements in that directions are particularly welcome␈↓.

␈↓ ↓H␈↓α␈↓ ¬?HISTORY OF LISP

␈↓ ↓H␈↓1. Introduction.

␈↓ ↓H␈↓␈↓ α_This␈α∩paper␈α∪concentrates␈α∩on␈α∩the␈α∪development␈α∩of␈α∩the␈α∪basic␈α∩ideas␈α∩and␈α∪distinguishes␈α∩two
␈↓ ↓H␈↓periods␈α-␈αSummer␈α1956␈αthrough␈αSummer␈α1958␈αwhen␈αthe␈αkey␈αideas␈αwere␈αdeveloped,␈αand␈αFall␈α
1958
␈↓ ↓H␈↓through␈α⊂1962␈α⊂when␈α⊂the␈α⊂programming␈α⊃language␈α⊂was␈α⊂implemented␈α⊂and␈α⊂applied␈α⊂to␈α⊃problems␈α⊂of
␈↓ ↓H␈↓artificial␈α
intelligence.␈α The␈α
scope␈α
of␈αthis␈α
conference␈α
does␈αnot␈α
go␈α
beyond␈αthat␈α
period,␈α
and␈αanyway
␈↓ ↓H␈↓after␈α
1962,␈αthe␈α
development␈αof␈α
LISP␈αbecame␈α
multi-stranded␈αwith␈α
different␈αideas␈α
being␈αpursued␈α
in
␈↓ ↓H␈↓different places.

␈↓ ↓H␈↓␈↓ α_As␈αa␈αprogramming␈αlanguage,␈αLISP␈αis␈αcharacterized␈αby␈αthe␈αfollowing␈αideas:␈α computing␈αwith
␈↓ ↓H␈↓symbolic␈α∪expressions␈α∪rather␈α∪than␈α∪numbers,␈α∪representation␈α∪of␈α∪symbolic␈α∪expressions␈α∪and␈α∩other
␈↓ ↓H␈↓information␈α⊃by␈α∩list␈α⊃structure␈α⊃in␈α∩the␈α⊃memory␈α∩of␈α⊃a␈α⊃computer,␈α∩representation␈α⊃of␈α∩information␈α⊃in
␈↓ ↓H␈↓external␈α∞media␈α∞by␈α∞atoms␈α∞and␈α∞lists␈α∞and␈α
secondarily␈α∞by␈α∞S-expressions,␈α∞a␈α∞small␈α∞set␈α∞of␈α∞selector␈α
and
␈↓ ↓H␈↓constructor␈αoperations␈αexpressed␈αas␈αfunctions,␈αcomposition␈αof␈αfunctions␈αas␈αa␈αtool␈αfor␈αforming␈α
more
␈↓ ↓H␈↓complex␈α⊗functions,␈α⊗the␈α⊗use␈α⊗of␈α∃conditional␈α⊗expressions␈α⊗for␈α⊗getting␈α⊗branching␈α⊗into␈α∃function
␈↓ ↓H␈↓definitions,␈α↔the␈α⊗recursive␈α↔use␈α⊗of␈α↔conditional␈α↔expressions␈α⊗as␈α↔a␈α⊗sufficient␈α↔tool␈α↔for␈α⊗building
␈↓ ↓H␈↓computable␈α
functions,␈αthe␈α
use␈αof␈α
λ-expressions␈α
for␈αnaming␈α
functions,␈αthe␈α
representation␈α
of␈αLISP
␈↓ ↓H␈↓programs␈α⊃as␈α⊃LISP␈α⊃data,␈α⊃the␈α⊃conditional␈α⊃expression␈α⊃interpretation␈α⊃of␈α⊃Boolean␈α⊃connectives,␈α⊃the
␈↓ ↓H␈↓LISP␈αfunction␈α␈↓↓eval␈↓␈αthat␈αserves␈αboth␈αas␈αa␈αformal␈αdefinition␈αof␈αthe␈αlanguage␈αand␈αas␈αan␈αinterpreter,
␈↓ ↓H␈↓and␈α∂garbage␈α∞collection␈α∂as␈α∂a␈α∞means␈α∂of␈α∂handling␈α∞the␈α∂erasure␈α∂problem.␈α∞ LISP␈α∂statements␈α∂are␈α∞also
␈↓ ↓H␈↓used as a command language when LISP is used in a time-sharing environment.

␈↓ ↓H␈↓␈↓ α_Some␈αof␈αthese␈αideas␈αwere␈αtaken␈αfrom␈α
other␈αlanguages␈αbut␈αmost␈αwere␈αnew.␈α Towards␈αthe␈α
end
␈↓ ↓H␈↓of␈αthe␈αinitial␈αperiod,␈αit␈αbecame␈αclear␈αthat␈αthis␈αcombination␈αof␈αideas␈αmade␈αan␈αelegant␈αmathematical
␈↓ ↓H␈↓system␈αas␈αwell␈αas␈αa␈αpractical␈αprogramming␈αlanguage.␈α Then␈αmathematical␈αneatness␈αbecame␈αa␈αgoal
␈↓ ↓H␈↓and␈α
led␈α
to␈α
pruning␈α
some␈α
features␈α
from␈α
the␈α
core␈α
of␈α
the␈α
language.␈α
 This␈α
was␈α
partly␈α
motivated␈α
by
␈↓ ↓H␈↓esthetic␈αreasons␈αand␈α
partly␈αby␈αthe␈αbelief␈α
that␈αit␈αwould␈αbe␈α
easier␈αto␈αdevise␈αtechniques␈α
for␈αproving
␈↓ ↓H␈↓programs correct if the semantics were compact and without exceptions.

␈↓ ↓H␈↓2. LISP prehistory - Summer 1956 through Summer 1958.

␈↓ ↓H␈↓␈↓ α_The␈α
desire␈α
to␈αdesign␈α
a␈α
list␈α
processing␈αlanguage␈α
for␈α
artificial␈αintelligence␈α
work␈α
on␈α
the␈αIBM
␈↓ ↓H␈↓704␈α⊂computer␈α⊃arose␈α⊂in␈α⊃the␈α⊂summer␈α⊃of␈α⊂1956␈α⊃at␈α⊂the␈α⊃time␈α⊂of␈α⊃the␈α⊂Dartmouth␈α⊃Summer␈α⊂Research
␈↓ ↓H␈↓Project␈α⊃on␈α⊃Artificial␈α⊃Intelligence.␈α⊃ The␈α⊃suitability␈α∩of␈α⊃list␈α⊃processing␈α⊃for␈α⊃AI␈α⊃research␈α∩was␈α⊃first
␈↓ ↓H␈↓pointed␈αout␈αby␈αNewell,␈α
Shaw␈αand␈αSimon␈αwhen␈αthey␈α
described␈αtheir␈αLogic␈αTheorist␈α
program␈αand
␈↓ ↓H␈↓its␈α∞implementation␈α∞in␈α∞IPL␈α∞2␈α∞on␈α∞the␈α∞JOHNNIAC␈α∞computer␈α∞at␈α∞RAND␈α∞Corporation.␈α∞ There␈α
was
␈↓ ↓H␈↓little␈αtemptation␈αto␈αcopy␈αIPL,␈αbecause␈αits␈α
form␈αwas␈αbased␈αon␈αa␈αJOHNNIAC␈αloader␈αthat␈α
happened
␈↓ ↓H␈↓to␈αbe␈αavailable␈αto␈αthem,␈αand␈αbecause␈αthe␈αFORTRAN␈αidea␈αof␈αwriting␈αprograms␈αalgebraically␈αwas
␈↓ ↓H␈↓attractive.␈α⊃ It␈α⊃was␈α⊃immediately␈α⊃apparent␈α⊂that␈α⊃arbitrary␈α⊃subexpressions␈α⊃of␈α⊃symbolic␈α⊂expressions
␈↓ ↓H␈↓could␈α∂be␈α∂obtained␈α∂by␈α∂composing␈α∂the␈α∂functions␈α∂that␈α∂extract␈α∂immediate␈α∂subexpressions,␈α⊂and␈α∂this
␈↓ ↓H␈↓seemed reason enough to go to an algebraic language.

␈↓ ↓H␈↓␈↓ α_There␈α
were␈α
two␈α
motivations␈α
for␈α
developing␈α
a␈αlanguage␈α
for␈α
the␈α
IBM␈α
704.␈α
 First,␈α
IBM␈αhad
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓generously␈α
undertaken␈αto␈α
establish␈αa␈α
New␈α
England␈αComputation␈α
Center␈αat␈α
M.I.T.,␈αand␈α
Dartmouth
␈↓ ↓H␈↓would␈α∩be␈α∩able␈α∩to␈α∩use␈α∩it.␈α∩ Second,␈α⊃IBM␈α∩was␈α∩undertaking␈α∩to␈α∩develop␈α∩a␈α∩program␈α∩for␈α⊃proving
␈↓ ↓H␈↓theorems␈α∂in␈α⊂plane␈α∂geometry␈α⊂(based␈α∂on␈α⊂an␈α∂idea␈α⊂of␈α∂Marvin␈α⊂Minsky's),␈α∂and␈α⊂I␈α∂was␈α⊂to␈α∂serve␈α⊂as␈α∂a
␈↓ ↓H␈↓consultant␈α
to␈α
that␈αproject.␈α
 At␈α
the␈αtime,␈α
IBM␈α
looked␈αlike␈α
a␈α
good␈αbet␈α
to␈α
pursue␈αartificial␈α
intelligence
␈↓ ↓H␈↓research␈αvigorously,␈αand␈αfurther␈αprojects␈αwere␈αexpected.␈α Moreover,␈αmy␈αown␈αresearch␈αin␈αartificial
␈↓ ↓H␈↓intelligence␈αwas␈α
proceeding␈αalong␈αthe␈α
lines␈αthat␈αled␈α
to␈αthe␈αAdvice␈α
Taker␈αproposal␈αin␈α
1958.␈α This
␈↓ ↓H␈↓project␈α⊃involved␈α∩representing␈α⊃information␈α∩about␈α⊃the␈α⊃world␈α∩by␈α⊃sentences␈α∩in␈α⊃a␈α∩suitable␈α⊃formal
␈↓ ↓H␈↓language␈α
and␈α
deciding␈α
what␈αto␈α
do␈α
by␈α
drawing␈αlogical␈α
consequences.␈α
 Representing␈α
sentences␈αby␈α
list
␈↓ ↓H␈↓structure␈αseemed␈αappropriate␈α-␈αit␈αstill␈αis␈α-␈αand␈αa␈αlist␈αprocessing␈αlanguage␈αalso␈αseemed␈αappropriate
␈↓ ↓H␈↓for programming the operations involved in deduction.

␈↓ ↓H␈↓␈↓ α_The␈α
first␈α
problem␈α
was␈α
to␈α
decide␈α
how␈α
to␈α
do␈α
list␈α
structure␈α
in␈α
the␈α
IBM␈α
704.␈α
 This␈α
computer
␈↓ ↓H␈↓has␈αa␈α36␈αbit␈αword,␈αand␈αtwo␈α15␈α
bit␈αparts,␈αcalled␈αthe␈αaddress␈αand␈αdecrement␈αwere␈α
distinguished␈αby
␈↓ ↓H␈↓special␈α⊃instructions␈α⊃form␈α⊃moving␈α⊃their␈α⊃contents␈α⊃to␈α⊂and␈α⊃from␈α⊃the␈α⊃15␈α⊃bit␈α⊃index␈α⊃registers.␈α⊂ The
␈↓ ↓H␈↓address␈α
of␈α
the␈αmachine␈α
was␈α
15␈α
bits,␈αso␈α
it␈α
was␈αclear␈α
that␈α
list␈α
structure␈αshould␈α
use␈α
15␈α
bit␈αpointers.
␈↓ ↓H␈↓Therefore,␈α⊂it␈α⊂was␈α⊂natural␈α⊂to␈α⊂consider␈α⊂the␈α⊂word␈α⊂as␈α⊂divided␈α⊂into␈α⊂4␈α⊂parts,␈α⊂the␈α⊂address␈α⊂part,␈α⊂the
␈↓ ↓H␈↓decrement␈αpart,␈α
the␈αprefix␈αpart␈α
and␈αthe␈αtag␈α
part.␈α The␈αlast␈α
two␈αwere␈αthree␈α
bits␈αeach␈αand␈α
separated
␈↓ ↓H␈↓from␈αeach␈αother␈αby␈αthe␈αdecrement␈αso␈αthat␈αthey␈αcould␈αnot␈αbe␈αeasily␈αcombined␈αinto␈αa␈αsingle␈α
six␈αbit
␈↓ ↓H␈↓part.

␈↓ ↓H␈↓␈↓ α_At␈αthis␈αpoint␈αthere␈αwas␈αsome␈α
indecision␈αabout␈αwhat␈αthe␈αbasic␈αoperators␈αshould␈α
be,␈αbecause
␈↓ ↓H␈↓the␈α∞operation␈α∂of␈α∞extracting␈α∞a␈α∂part␈α∞of␈α∞the␈α∂word␈α∞by␈α∞masking␈α∂was␈α∞considered␈α∞separately␈α∂from␈α∞the
␈↓ ↓H␈↓operation␈αof␈αtaking␈αthe␈αcontents␈αof␈αa␈αword␈αin␈α
memory␈αas␈αa␈αfunction␈αof␈αits␈αaddress.␈α At␈αthe␈αtime,␈α
it
␈↓ ↓H␈↓seemed␈α⊂dubious␈α⊂to␈α⊂regard␈α⊂the␈α⊂latter␈α⊂operation␈α⊂as␈α⊂a␈α⊂function,␈α⊂since␈α⊂its␈α⊂value␈α⊂depended␈α⊂on␈α∂the
␈↓ ↓H␈↓contents␈α⊃of␈α∩memory␈α⊃at␈α∩the␈α⊃time␈α∩the␈α⊃operation␈α⊃was␈α∩performed,␈α⊃so␈α∩it␈α⊃didn't␈α∩act␈α⊃like␈α∩a␈α⊃proper
␈↓ ↓H␈↓mathematical␈α
function.␈α
 However,␈α
the␈α
advantages␈α
of␈αtreating␈α
it␈α
grammatically␈α
as␈α
a␈α
function␈αso␈α
that
␈↓ ↓H␈↓it could be composed were also apparent.

␈↓ ↓H␈↓␈↓ α_Therefore,␈αthe␈α
initial␈αset␈αof␈α
functions␈αincluded␈α␈↓↓cwr␈↓,␈α
standing␈αfor␈α"Contents␈α
of␈αthe␈α
Word␈αin
␈↓ ↓H␈↓Register␈α
number"␈αand␈α
four␈αfunctions␈α
that␈αextracted␈α
the␈αparts␈α
of␈αthe␈α
word␈αand␈α
shifted␈αthem␈α
to␈αa
␈↓ ↓H␈↓standard␈αposition␈α
at␈αthe␈αright␈α
of␈αthe␈α
word.␈α An␈αadditional␈α
function␈αof␈α
three␈αarguments␈αthat␈α
would
␈↓ ↓H␈↓also extract an arbitrary bit sequence was thrown in just in case it might be useful.

␈↓ ↓H␈↓␈↓ α_It␈αwas␈αsoon␈αnoticed␈αthat␈αextraction␈α
of␈αa␈αsubexpression␈αinvolved␈αcomposing␈αthe␈αextraction␈α
of
␈↓ ↓H␈↓the␈αaddress␈αpart␈αwith␈α␈↓↓cwr␈↓␈αand␈αthat␈αcontinuing␈αalong␈αthe␈αlist␈αinvolved␈αcomposing␈αthe␈αextraction␈αof
␈↓ ↓H␈↓the␈α∩decrement␈α∩part␈α∪with␈α∩␈↓↓cwr␈↓.␈α∩ Therefore,␈α∪the␈α∩compounds␈α∩␈↓↓car␈↓,␈α∪standing␈α∩for␈α∩"Contents␈α∪of␈α∩the
␈↓ ↓H␈↓Address␈α∞part␈α∂of␈α∞Register␈α∂number",␈α∞and␈α∂its␈α∞analogs␈α∂␈↓↓cdr␈↓,␈α∞␈↓↓cpr␈↓,␈α∂and␈α∞␈↓↓ctr␈↓␈α∂were␈α∞defined.␈α∂ A␈α∞construct
␈↓ ↓H␈↓operation␈αfor␈α
taking␈αa␈α
word␈αoff␈α
the␈αfree␈α
storage␈αlist␈α
and␈αstuffing␈α
it␈αwith␈α
given␈αcontents␈α
was␈αalso
␈↓ ↓H␈↓obviously␈α∪required.␈α∩ At␈α∪some␈α∩point␈α∪a␈α∪␈↓↓cons(a,d,p,t)␈↓␈α∩was␈α∪defined,␈α∩but␈α∪it␈α∩was␈α∪regarded␈α∪as␈α∩a
␈↓ ↓H␈↓subroutine␈αand␈αnot␈αas␈αa␈αfunction␈αwith␈αa␈αvalue.␈α This␈αwork␈αwas␈αdone␈αat␈αDartmouth,␈αbut␈αnot␈αon␈αa
␈↓ ↓H␈↓computer,␈α
since␈α
the␈α
New␈α
England␈α
Computation␈α
Center␈α
was␈α
not␈α
expected␈α
to␈α
receive␈α
its␈α∞IBM␈α
704
␈↓ ↓H␈↓for another year.

␈↓ ↓H␈↓␈↓ α_In␈αconnection␈αwith␈αthe␈αplane␈αgeometry␈αproject␈αit␈αwas␈αdecided␈αto␈αimplement␈αa␈αlist␈αprocessing
␈↓ ↓H␈↓language␈α∞within␈α∞FORTRAN,␈α∞because␈α∞this␈α∞seemed␈α∞to␈α∂the␈α∞the␈α∞easiest␈α∞way␈α∞to␈α∞get␈α∞started,␈α∂and,␈α∞in
␈↓ ↓H␈↓those␈α
days,␈α∞writing␈α
a␈α∞compiler␈α
for␈α∞a␈α
new␈α∞language␈α
was␈α∞believed␈α
to␈α∞take␈α
many␈α∞man-years.␈α
 This
␈↓ ↓H␈↓work␈α∩was␈α∩undertaken␈α∩by␈α∪Herbert␈α∩Gelernter␈α∩and␈α∩Carl␈α∩Gerberick␈α∪at␈α∩IBM␈α∩and␈α∩led␈α∪to␈α∩FLPL,
␈↓ ↓H␈↓standing␈α∞for␈α∞FORTRAN␈α∞List␈α∞Processing␈α∞Language.␈α∞ Gelernter␈α∞and␈α∞Gerberick␈α∞noticed␈α∞that␈α
␈↓↓cons␈↓
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓should␈αbe␈αa␈αfunction,␈αnot␈αjust␈αa␈αsubroutine,␈αand␈αthat␈αits␈αvalue␈αshould␈αbe␈αthe␈αlocation␈αof␈αthe␈αword
␈↓ ↓H␈↓that␈α
had␈α
been␈α
stuffed.␈α
 This␈α
permitted␈αnew␈α
expressions␈α
to␈α
be␈α
constructed␈α
out␈αof␈α
subsubexpressions
␈↓ ↓H␈↓by composing occurrences of ␈↓↓cons␈↓.

␈↓ ↓H␈↓␈↓ α_While␈α∞expressions␈α∞could␈α∞be␈α∞handled␈α∞easily␈α∞in␈α∞FLPL,␈α∞and␈α∞it␈α∞was␈α∞used␈α∞successfully␈α∞for␈α∞the
␈↓ ↓H␈↓Geometry␈αprogram,␈αit␈αhad␈αneither␈αconditional␈αexpressions␈αnor␈αrecursion,␈αand␈αerasing␈αlist␈αstructure
␈↓ ↓H␈↓was handled explicitly by the program.

␈↓ ↓H␈↓␈↓ α_Conditional␈αexpressions␈αwere␈αinvented␈αin␈αconnection␈α
with␈αa␈αset␈αof␈αchess␈αlegal␈αmove␈α
routines
␈↓ ↓H␈↓being␈αwritten␈αin␈αFORTRAN␈αfor␈αthe␈αIBM␈α
704␈αat␈αM.I.T.␈αduring␈α1957-58.␈α This␈αprogram␈α
did␈αnot
␈↓ ↓H␈↓use␈α∂list-processing.␈α∂ The␈α∂IF␈α∂statement␈α∂provided␈α∂in␈α∂FORTRAN␈α∂1␈α∂and␈α∂FORTRAN␈α∂2␈α∂was␈α∞very
␈↓ ↓H␈↓awkward␈α
to␈α
use,␈α
and␈α
it␈αwas␈α
natural␈α
to␈α
invent␈α
a␈αfunction␈α
XIF(M,N1,N2)␈α
whose␈α
value␈α
was␈α
N1␈αor
␈↓ ↓H␈↓N2␈α∩according␈α⊃to␈α∩whether␈α⊃the␈α∩expression␈α⊃M␈α∩was␈α⊃zero␈α∩or␈α⊃not.␈α∩ The␈α⊃function␈α∩shortened␈α⊃many
␈↓ ↓H␈↓programs␈αand␈αmade␈αthem␈αeasier␈αto␈αunderstand,␈αbut␈αit␈αhad␈αto␈αbe␈αused␈αsparingly,␈αbecause␈αall␈αthree
␈↓ ↓H␈↓arguments␈α∂had␈α⊂to␈α∂be␈α⊂evaluated␈α∂before␈α⊂XIF␈α∂was␈α⊂entered,␈α∂since␈α⊂XIF␈α∂was␈α⊂called␈α∂as␈α⊂an␈α∂ordinary
␈↓ ↓H␈↓FORTRAN␈αfunction␈αthough␈αwritten␈αin␈αmachine␈αlanguage.␈α This␈αled␈αto␈αthe␈αinvention␈αof␈αthe␈αtrue
␈↓ ↓H␈↓conditional␈αexpression␈αwhich␈αevaluates␈αonly␈αone␈αof␈αN1␈αand␈αN2␈αaccording␈αto␈αwhether␈αM␈αis␈αtrue␈α
or
␈↓ ↓H␈↓false and to a desire for a programming language that would allow its use.

␈↓ ↓H␈↓␈↓ α_A␈αpaper␈αdefining␈αconditional␈αexpressions␈αand␈αproposing␈αtheir␈αuse␈αin␈αAlgol␈αwas␈αsent␈α
to␈αthe
␈↓ ↓H␈↓␈↓↓Communications␈α
of␈α
the␈α
ACM␈↓␈αbut␈α
was␈α
arbitrarily␈α
demoted␈αto␈α
a␈α
letter␈α
to␈αthe␈α
editor,␈α
because␈α
it␈αwas
␈↓ ↓H␈↓very short.

␈↓ ↓H␈↓␈↓ α_I␈α∂spent␈α∂the␈α∞summer␈α∂of␈α∂1958␈α∞at␈α∂IBM␈α∂and␈α∞was␈α∂attracted␈α∂to␈α∞the␈α∂problem␈α∂of␈α∞differentiating
␈↓ ↓H␈↓algebraic␈α~expressions␈α→as␈α~an␈α~example␈α→of␈α~symbolic␈α~computation.␈α→ The␈α~single␈α~example␈α→of
␈↓ ↓H␈↓differentiation led to the following innovations:

␈↓ ↓H␈↓␈↓ α_a.␈α∃Writing␈α∃recursive␈α∃function␈α∃definitions␈α∃using␈α∃conditional␈α∃expressions.␈α∃ The␈α∃idea␈α∀of
␈↓ ↓H␈↓differentiation␈α⊂is␈α⊂obviously␈α∂recursive,␈α⊂and␈α⊂conditional␈α∂expressions␈α⊂allowed␈α⊂combining␈α⊂the␈α∂cases
␈↓ ↓H␈↓into a single formula.

␈↓ ↓H␈↓␈↓ α_b.␈α∞The␈α∞␈↓↓maplist␈↓␈α∞function␈α∞that␈α∞forms␈α∞a␈α
list␈α∞of␈α∞applications␈α∞of␈α∞a␈α∞functional␈α∞argument␈α∞to␈α
the
␈↓ ↓H␈↓elements␈αof␈αa␈αlist.␈α This␈αwas␈αobviously␈αwanted␈αfor␈αdifferentiating␈αsums␈αof␈αarbitrarily␈αmany␈αterms.
␈↓ ↓H␈↓With␈α⊂a␈α∂slight␈α⊂modification␈α∂to␈α⊂its␈α∂present␈α⊂form␈α∂that␈α⊂takes␈α∂tails␈α⊂of␈α∂the␈α⊂list␈α∂as␈α⊂arguments␈α⊂of␈α∂the
␈↓ ↓H␈↓function, it could be applied to differentiating products.

␈↓ ↓H␈↓␈↓ α_c.␈α
If␈α
one␈α
is␈α
to␈α∞use␈α
functions␈α
as␈α
arguments,␈α
then␈α
one␈α∞needs␈α
a␈α
notation␈α
for␈α
functions,␈α∞and␈α
it
␈↓ ↓H␈↓seemed␈αnatural␈αto␈αuse␈αthe␈αλ-notation␈αof␈αChurch.␈α I␈αdidn't␈αunderstand␈αthe␈αrest␈αof␈αhis␈αbook␈α␈↓↓Calculi
␈↓ ↓H␈↓↓of␈α∞Lambda␈α
Conversion␈↓,␈α∞so␈α
I␈α∞wasn't␈α
tempted␈α∞to␈α
try␈α∞to␈α
implement␈α∞his␈α
more␈α∞general␈α∞mechanism␈α
for
␈↓ ↓H␈↓defining␈α⊃functions.␈α⊃ It␈α⊂used␈α⊃higher␈α⊃order␈α⊃functionals␈α⊂instead␈α⊃of␈α⊃using␈α⊃conditional␈α⊂expressions.
␈↓ ↓H␈↓Conditional expressions are much more readily implemented on computers.

␈↓ ↓H␈↓␈↓ α_d.␈αThe␈αrecursive␈αdefinition␈αof␈α
differentiation␈αmade␈αno␈αprovision␈αfor␈αerasure␈α
of␈αabandoned
␈↓ ↓H␈↓list␈α⊂structure.␈α∂ No␈α⊂solution␈α∂was␈α⊂apparent␈α∂at␈α⊂the␈α∂time,␈α⊂but␈α∂the␈α⊂idea␈α∂of␈α⊂complicating␈α⊂the␈α∂elegant
␈↓ ↓H␈↓definition of differentiation by putting in explicit erasure was unattractive.

␈↓ ↓H␈↓␈↓ α_The␈α⊃differentiation␈α⊂program␈α⊃was␈α⊃not␈α⊂actually␈α⊃implemented␈α⊂that␈α⊃summer,␈α⊃because␈α⊂FLPL
␈↓ ↓H␈↓allowed neither conditional expressions nor recursive use of subroutines.
␈↓ ↓H␈↓␈↓ εH␈↓ 93


␈↓ ↓H␈↓2. The implementation of LISP.

␈↓ ↓H␈↓␈↓ α_In␈α∞the␈α∞Fall␈α∂of␈α∞1958,␈α∞I␈α∂became␈α∞Assistant␈α∞Professor␈α∞of␈α∂Communication␈α∞Sciences␈α∞(in␈α∂the␈α∞EE
␈↓ ↓H␈↓Department)␈α∪at␈α∪M.I.T.,␈α∪and␈α∪Marvin␈α∪Minsky␈α∪(then␈α∪an␈α∪assistant␈α∪professor␈α∪in␈α∪the␈α∩Mathemtics
␈↓ ↓H␈↓Department)␈α
and␈α∞I␈α
started␈α
the␈α∞M.I.T.␈α
Artificial␈α
Intelligence␈α∞Project.␈α
 The␈α
Project␈α∞was␈α
supported
␈↓ ↓H␈↓by␈α
the␈α
M.I.T.␈α
Research␈αLaboratory␈α
of␈α
Electronics␈α
which␈α
had␈αa␈α
contract␈α
from␈α
the␈α
armed␈αservices
␈↓ ↓H␈↓that␈αpermitted␈αgreat␈αfreedom␈αto␈αthe␈αDirector,␈αProfessor␈αJerome␈αWiesner,␈αin␈αinitiating␈αnew␈αprojects
␈↓ ↓H␈↓that␈α∂seemed␈α∞to␈α∂him␈α∂of␈α∞scientific␈α∂interest.␈α∂ No␈α∞written␈α∂proposal␈α∂was␈α∞ever␈α∂made.␈α∂ When␈α∞Wiesner
␈↓ ↓H␈↓asked␈αMinsky␈αand␈αme␈αwhat␈αwe␈αneeded␈αfor␈αthe␈αproject,␈αwe␈αasked␈αfor␈αa␈αroom,␈αtwo␈αprogrammers,␈αa
␈↓ ↓H␈↓secretary␈α
and␈α
a␈α
keypunch,␈αand␈α
we␈α
were␈α
asked␈α
whether␈αwe␈α
would␈α
also␈α
undertake␈α
the␈αsupervision␈α
of
␈↓ ↓H␈↓some of the six mathematics graduate students that R.L.E had undertaken to support.

␈↓ ↓H␈↓␈↓ α_The␈α∩implementation␈α∩of␈α⊃LISP␈α∩was␈α∩undertaken␈α⊃in␈α∩Fall␈α∩1958.␈α⊃ The␈α∩original␈α∩idea␈α∩was␈α⊃to
␈↓ ↓H␈↓produce␈α⊗a␈α⊗compiler,␈α∃but␈α⊗this␈α⊗was␈α∃considered␈α⊗a␈α⊗major␈α∃undertaking,␈α⊗and␈α⊗we␈α⊗needed␈α∃some
␈↓ ↓H␈↓experimenting␈α∪in␈α∪order␈α∪to␈α∩get␈α∪good␈α∪conventions␈α∪for␈α∩subroutine␈α∪linking,␈α∪stack␈α∪handling␈α∩and
␈↓ ↓H␈↓erasure.␈α Therefore,␈α
we␈αstarted␈αby␈α
hand-compiling␈αvarious␈αfunctions␈α
into␈αassembly␈α
language␈αand
␈↓ ↓H␈↓writing␈α⊂subroutines␈α⊂to␈α⊂provide␈α⊂a␈α⊂LISP␈α⊂"environment".␈α⊂ These␈α⊂included␈α⊂programs␈α⊂to␈α⊃read␈α⊂and
␈↓ ↓H␈↓print␈αlist␈αstructure.␈α I␈αcan't␈αnow␈αremember␈αwhether␈αthe␈αdecision␈αto␈αuse␈αparenthesized␈αlist␈αnotation
␈↓ ↓H␈↓as␈α⊃the␈α⊃external␈α⊃form␈α⊃of␈α⊃LISP␈α⊃data␈α⊃was␈α⊃made␈α⊃then␈α⊃or␈α⊃whether␈α⊃it␈α⊃had␈α⊃already␈α⊃been␈α⊃used␈α⊂in
␈↓ ↓H␈↓discussing␈α∂the␈α∂paper␈α∂differentiation␈α∞program.␈α∂ The␈α∂erasure␈α∂problem␈α∞also␈α∂had␈α∂to␈α∂be␈α∞considered,
␈↓ ↓H␈↓and it was clearly unaesthetic to use explicit erasure as did IPL.  There were two alternatives.

␈↓ ↓H␈↓␈↓ α_The␈α
first␈α
alternative␈α
was␈α
to␈α
erase␈α
the␈αold␈α
contents␈α
of␈α
a␈α
program␈α
variable␈α
whenever␈α
it␈αwas
␈↓ ↓H␈↓updated.␈α Since␈αthe␈α
␈↓↓car␈↓␈αand␈α␈↓↓cdr␈↓␈α
operations␈αwere␈αnot␈α
to␈αcopy␈αstructure,␈α
merging␈αlist␈αstructure␈α
would
␈↓ ↓H␈↓occur,␈α∞and␈α∞so␈α∞that␈α∞erasure␈α∞would␈α∞have␈α
required␈α∞a␈α∞system␈α∞of␈α∞reference␈α∞counts.␈α∞ Since␈α∞there␈α
were
␈↓ ↓H␈↓only␈α
six␈α
bits␈α
left␈α
in␈α
a␈α
word,␈α
and␈α
these␈α
were␈α
in␈α
separated␈α
parts␈α
of␈α
the␈α
word,␈α
reference␈αcounts␈α
seemed
␈↓ ↓H␈↓infeasible without a drastic change in the way list structures were represented.

␈↓ ↓H␈↓␈↓ α_The␈α∞second␈α∂alternative␈α∞is␈α∂␈↓↓garbage␈α∞collection␈↓␈α∂in␈α∞which␈α∂storage␈α∞is␈α∂abandoned␈α∞until␈α∂the␈α∞free
␈↓ ↓H␈↓storage␈α
list␈α
is␈α
exhausted,␈α
the␈α
storage␈α
accessible␈α
from␈α
program␈α
variables␈α
and␈α
the␈α
stack␈α
is␈α
marked,
␈↓ ↓H␈↓and␈α∂the␈α∂unmarked␈α∂storage␈α∂is␈α∂made␈α∂into␈α∂a␈α∂new␈α∂free␈α∂storage␈α∂list.␈α∂ Once␈α∂we␈α∂decided␈α∂on␈α∞garbage
␈↓ ↓H␈↓collection,␈α∂its␈α∂actual␈α∂implementation␈α∂could␈α∂be␈α∞postponed,␈α∂because␈α∂only␈α∂toy␈α∂examples␈α∂were␈α∞being
␈↓ ↓H␈↓done.␈α (A␈αlist␈αhandling␈αscheme␈αusing␈αreference␈αcounts␈αwas␈αlater␈αused␈αby␈αCollins␈αon␈αa␈α48␈αbit␈αCDC
␈↓ ↓H␈↓computer).

␈↓ ↓H␈↓␈↓ α_At␈α∂that␈α∞time␈α∂it␈α∞was␈α∂also␈α∞decided␈α∂to␈α∞use␈α∂SAVE␈α∞and␈α∂UNSAVE␈α∞routines␈α∂that␈α∞use␈α∂a␈α∞single
␈↓ ↓H␈↓public␈α∪stack␈α∪in␈α∀order␈α∪save␈α∪the␈α∀values␈α∪of␈α∪variables␈α∪and␈α∀subroutine␈α∪return␈α∪addresses␈α∀in␈α∪the
␈↓ ↓H␈↓implementation␈αof␈αrecursive␈α
subroutines.␈α IPL␈αbuilt␈α
stacks␈αas␈αlist␈α
structure␈αand␈αtheir␈α
use␈αhad␈αto␈α
be
␈↓ ↓H␈↓explicitly␈αprogrammed.␈α Another␈αdecision␈αwas␈αto␈αgive␈αup␈αthe␈αprefix␈αand␈αtag␈αparts␈αof␈αthe␈αword,␈αto
␈↓ ↓H␈↓abandon␈α␈↓↓cwr␈↓,␈αand␈αto␈αmake␈α␈↓↓cons␈↓␈αa␈αfunction␈αof␈αtwo␈αarguments.␈α This␈αleft␈αus␈αwith␈αonly␈αa␈αsingle␈αtype
␈↓ ↓H␈↓- the 15 bit address - so that the language didn't require types.

␈↓ ↓H␈↓␈↓ α_These␈α⊃simplifications␈α⊃made␈α∩LISP␈α⊃into␈α⊃a␈α⊃way␈α∩of␈α⊃describing␈α⊃computable␈α∩functions␈α⊃much
␈↓ ↓H␈↓neater␈α∩than␈α⊃the␈α∩Turing␈α⊃machines␈α∩or␈α⊃general␈α∩recursive␈α⊃definitions␈α∩used␈α⊃in␈α∩recursive␈α⊃function
␈↓ ↓H␈↓theory.␈α⊂ The␈α∂fact␈α⊂that␈α∂Turing␈α⊂machines␈α∂constitute␈α⊂an␈α∂awkward␈α⊂programming␈α⊂language␈α∂doesn't
␈↓ ↓H␈↓much␈α⊂bother␈α∂recursive␈α⊂function␈α⊂theorists,␈α∂because␈α⊂they␈α∂almost␈α⊂never␈α⊂have␈α∂any␈α⊂reason␈α⊂to␈α∂write
␈↓ ↓H␈↓particular␈α∂recursive␈α∂definitions,␈α∂since␈α∂the␈α∂theory␈α∂concerns␈α∂recursive␈α∂functions␈α∂in␈α⊂general.␈α∂ They
␈↓ ↓H␈↓often␈αhave␈αreason␈αto␈αprove␈αthat␈αrecursive␈αfunctions␈αwith␈αspecific␈αproperties␈αexist,␈αbut␈αthis␈αcan␈αbe
␈↓ ↓H␈↓␈↓ εH␈↓ 94


␈↓ ↓H␈↓done␈α
by␈αan␈α
informal␈α
argument␈αwithout␈α
having␈αto␈α
write␈α
them␈αdown␈α
explicitly.␈α
 In␈αthe␈α
early␈αdays␈α
of
␈↓ ↓H␈↓computing,␈αsome␈αpeople␈α
developed␈αprogramming␈αlanguages␈αbased␈α
on␈αTuring␈αmachines;␈αperhaps␈α
it
␈↓ ↓H␈↓seemed␈α∃more␈α⊗scientific.␈α∃ Anyway,␈α⊗I␈α∃decided␈α⊗to␈α∃write␈α∃a␈α⊗paper␈α∃describing␈α⊗LISP␈α∃both␈α⊗as␈α∃a
␈↓ ↓H␈↓programming␈α
language␈α
and␈αas␈α
a␈α
formalism␈αfor␈α
doing␈α
recursive␈αfunction␈α
theory.␈α
 The␈α
paper␈αwas
␈↓ ↓H␈↓␈↓↓Recursive␈α∪functions␈α∪of␈α∪symbolic␈α∩expressions␈α∪and␈α∪their␈α∪computation␈α∩by␈α∪machine,␈α∪part␈α∪I␈↓␈α∩which
␈↓ ↓H␈↓appeared␈α
in␈α
the␈α
␈↓↓Communications␈α
of␈α∞the␈α
ACM␈↓␈α
in␈α
April␈α
1960.␈α∞ Part␈α
II␈α
was␈α
never␈α
written␈α∞but␈α
was
␈↓ ↓H␈↓intended␈α⊂to␈α⊂contain␈α⊂applications␈α⊂to␈α⊂computing␈α⊂with␈α⊂algebraic␈α⊂expressions.␈α⊂ The␈α⊂paper␈α⊂had␈α⊂no
␈↓ ↓H␈↓influence␈α∂on␈α∞recursive␈α∂function␈α∞theorists,␈α∂because␈α∂it␈α∞didn't␈α∂address␈α∞the␈α∂questions␈α∂that␈α∞interested
␈↓ ↓H␈↓them.

␈↓ ↓H␈↓␈↓ α_One␈α∂way␈α∂to␈α∞show␈α∂that␈α∂LISP␈α∞was␈α∂neater␈α∂than␈α∞Turing␈α∂machines␈α∂was␈α∞to␈α∂write␈α∂a␈α∞universal
␈↓ ↓H␈↓LISP␈αfunction␈αand␈αshow␈αhow␈αmuch␈αbriefer␈αand␈αmore␈αcomprehensible␈αit␈αwas␈αthan␈αthe␈αdescription
␈↓ ↓H␈↓of␈αa␈αuniversal␈α
Turing␈αmachine.␈α This␈αwas␈α
the␈αLISP␈αfunction␈α␈↓↓eval[e,a]␈↓␈α
that␈αcomputes␈αthe␈αvalue␈α
of
␈↓ ↓H␈↓a␈α
LISP␈α
expression␈α
␈↓↓e␈↓␈α∞-␈α
the␈α
second␈α
argument␈α∞␈↓↓a␈↓␈α
being␈α
a␈α
list␈α∞of␈α
assignments␈α
of␈α
values␈α∞to␈α
variables
␈↓ ↓H␈↓needed␈α⊂to␈α⊃make␈α⊂the␈α⊂recursion␈α⊃work.␈α⊂ Writing␈α⊂␈↓↓eval␈↓␈α⊃required␈α⊂inventing␈α⊂a␈α⊃notation␈α⊂representing
␈↓ ↓H␈↓LISP␈α∂functions␈α∞as␈α∂LISP␈α∞data,␈α∂and␈α∞such␈α∂a␈α∞notation␈α∂was␈α∞devised␈α∂without␈α∞much␈α∂thought␈α∂for␈α∞the
␈↓ ↓H␈↓purposes␈αof␈αthe␈αpaper.␈α Logical␈αcompleteness␈αrequired␈αthat␈αthe␈αnotation␈αused␈αto␈αexpress␈αfunctions
␈↓ ↓H␈↓used␈α∂as␈α∞functional␈α∂arguments␈α∂be␈α∞extended␈α∂to␈α∞provide␈α∂for␈α∂recursive␈α∞functions,␈α∂and␈α∂the␈α∞LABEL
␈↓ ↓H␈↓notation␈α⊂was␈α⊂invented␈α⊂for␈α⊂that␈α⊂purpose.␈α⊂ D.M.R.␈α⊂Park␈α⊂pointed␈α⊂out␈α⊂that␈α⊂LABEL␈α⊂was␈α∂logically
␈↓ ↓H␈↓unnecessary␈α∃since␈α∀the␈α∃result␈α∀could␈α∃be␈α∃achieved␈α∀using␈α∃only␈α∀LAMBDA␈α∃-␈α∀albeit␈α∃in␈α∃a␈α∀more
␈↓ ↓H␈↓complicated␈αway.␈α S.R.␈αRussell,␈α
a␈αprogrammer␈αfor␈αthe␈αproject,␈α
noticed␈αthat␈α␈↓↓eval␈↓␈αcould␈αserve␈α
as␈αan
␈↓ ↓H␈↓interpreter␈αfor␈αLISP,␈αpromptly␈αhand␈αcoded␈αit,␈αand␈αwe␈αnow␈αhad␈αa␈αprogramming␈αlanguage␈αwith␈αan
␈↓ ↓H␈↓interpreter.

␈↓ ↓H␈↓␈↓ α_The␈α∞unexpected␈α∂appearance␈α∞of␈α∞an␈α∂interpreter␈α∞tended␈α∂to␈α∞freeze␈α∞the␈α∂form␈α∞of␈α∂the␈α∞language,
␈↓ ↓H␈↓and␈αsome␈αof␈αthe␈αdecisions␈αmade␈αrather␈αlightheartedly␈αfor␈αthe␈α"Recursive␈αfunctions␈α..."␈α
paper␈αlater
␈↓ ↓H␈↓proved␈αunfortunate.␈α These␈αincluded␈αthe␈αCOND␈αnotation␈αfor␈αconditional␈αexpressions␈αwhich␈αleads
␈↓ ↓H␈↓to␈αan␈αunnecessary␈αdepth␈αof␈αparentheses,␈αand␈αthe␈α
use␈αof␈αthe␈αnumber␈αzero␈αto␈αdenote␈αthe␈α
empty␈αlist
␈↓ ↓H␈↓NIL␈αand␈αthe␈αtruth␈αvalue␈α␈↓αfalse␈↓.␈α Besides␈αencouraging␈αpornographic␈αprogramming,␈αgiving␈αa␈αspecial
␈↓ ↓H␈↓interpretation to the address 0 has caused difficulties in all subsequent implementations.

␈↓ ↓H␈↓3. Improvements.  LISP I and LISP 1.5.

␈↓ ↓H␈↓␈↓ α_a.␈αProperty␈αlists.␈α The␈αidea␈αof␈αproviding␈αeach␈αatom␈αwith␈αa␈αlist␈αof␈αproperties␈αwas␈αpresent␈αin
␈↓ ↓H␈↓the␈αfirst␈αassembly␈αlanguage␈αimplementation.␈α
 It␈αwas␈αalso␈αone␈αof␈α
the␈αtheoretical␈αideas␈αof␈αthe␈α
Advice
␈↓ ↓H␈↓Taker,␈αalthough␈αthe␈αAdvice␈αTaker␈α(McCarthy␈α1959)␈αwould␈αhave␈αrequired␈αa␈αproperty␈αlist␈αfor␈αany
␈↓ ↓H␈↓expression␈α
for␈α
about␈α
which␈α
information␈α
was␈α∞known␈α
that␈α
did␈α
not␈α
follow␈α
from␈α
its␈α∞structure.␈α
 The
␈↓ ↓H␈↓READ␈α
and␈α
PRINT␈α
programs␈α
required␈α
that␈α
the␈α
print␈α
names␈α
of␈α
atoms␈α
be␈α
accessible,␈α
and␈α
as␈α
soon␈α
as
␈↓ ↓H␈↓function␈αdefinition␈αbecame␈αpossible,␈αit␈αwas␈αnecessary␈αto␈αindicate␈αwhether␈αa␈αfunction␈αwas␈αa␈αSUBR
␈↓ ↓H␈↓in␈α∞machine␈α
code␈α∞or␈α
was␈α∞an␈α
EXPR␈α∞represented␈α
by␈α∞list␈α
structure.␈α∞ Several␈α
functions␈α∞dealing␈α
with
␈↓ ↓H␈↓property lists were also made available for application programs which made heavy use of them.

␈↓ ↓H␈↓␈↓ α_b.␈αInsertion␈α
of␈αelements␈αin␈α
lists␈αand␈α
their␈αdeletion.␈α One␈α
of␈αthe␈α
original␈αadvertised␈αvirtues␈α
of
␈↓ ↓H␈↓list␈α∞processing␈α
for␈α∞AI␈α∞work␈α
was␈α∞the␈α
ability␈α∞to␈α∞insert␈α
and␈α∞delete␈α
elements␈α∞of␈α∞lists.␈α
 Unfortunately,
␈↓ ↓H␈↓this␈α⊃facility␈α⊃coexists␈α⊃uneasily␈α⊂with␈α⊃shared␈α⊃list␈α⊃structure.␈α⊂ Moreover,␈α⊃operations␈α⊃that␈α⊃insert␈α⊂and
␈↓ ↓H␈↓delete␈α⊂don't␈α⊂have␈α⊂a␈α⊂neat␈α⊂representation␈α⊂as␈α∂functions.␈α⊂ LISP␈α⊂contains␈α⊂them␈α⊂in␈α⊂the␈α⊂form␈α⊂of␈α∂the
␈↓ ↓H␈↓␈↓↓rplaca␈↓␈α⊗and␈α↔␈↓↓rplacd␈↓␈α⊗pseudo-functions,␈α⊗but␈α↔programs␈α⊗that␈α⊗use␈α↔them␈α⊗cannot␈α↔be␈α⊗conveniently
␈↓ ↓H␈↓represented␈α∞in␈α∞logic,␈α∞because,␈α∞regarded␈α∞as␈α∞functions,␈α∞they␈α∞don't␈α∞permit␈α∞replacement␈α∞of␈α∞equals␈α
by
␈↓ ↓H␈↓equals.
␈↓ ↓H␈↓␈↓ εH␈↓ 95


␈↓ ↓H␈↓␈↓ α_c.␈α
Numbers.␈α
 Many␈α
computations␈α
require␈α
both␈α
numbers␈α
and␈α
symbolic␈αexpressions.␈α
 Numbers
␈↓ ↓H␈↓were␈α⊃implemented␈α⊃in␈α⊃LISP␈α⊃I␈α⊃as␈α⊃lists␈α⊃of␈α∩atoms,␈α⊃and␈α⊃this␈α⊃was␈α⊃useless␈α⊃for␈α⊃all␈α⊃but␈α∩the␈α⊃simplest
␈↓ ↓H␈↓computations.␈α
 A␈α
reasonably␈α
efficient␈α
implementation␈α
of␈α
numbers␈α
as␈α
atoms␈α
in␈α
S-expressions␈α
was
␈↓ ↓H␈↓made␈α
in␈α
LISP␈α
1.5,␈α
but␈α
in␈α
all␈α
the␈α
early␈α
LISPs,␈α
numerical␈α
computations␈α
were␈α
still␈α
10␈α
to␈α∞100␈α
times
␈↓ ↓H␈↓slower␈αthan␈αin␈αFORTRAN.␈α Efficient␈αnumerical␈α
computation␈αrequires␈αsome␈αform␈αof␈αtyping␈αin␈α
the
␈↓ ↓H␈↓source␈α
language␈αand␈α
a␈α
distinction␈αbetween␈α
numbers␈α
treated␈αby␈α
themselves␈α
and␈αas␈α
elements␈α
of␈αS-
␈↓ ↓H␈↓expressions.

␈↓ ↓H␈↓␈↓ α_d.␈α∪Free␈α∪variables.␈α∪ In␈α∩all␈α∪innocence,␈α∪James␈α∪R.␈α∩Slagle␈α∪programmed␈α∪the␈α∪following␈α∩LISP
␈↓ ↓H␈↓function definition and complained when it didn't work right:

␈↓ ↓H␈↓␈↓ α_␈↓↓testr[x,p,f,u]␈α∀←␈α∀␈↓αif␈↓↓␈α∀p[x]␈α∀␈↓αthen␈↓↓␈α∀f[x]␈α∃␈↓αelse␈↓↓␈α∀␈↓αif␈↓↓␈α∀␈↓αa␈↓↓␈α∀x␈α∀␈↓αthen␈↓↓␈α∀u[]␈α∀␈↓αelse␈↓↓␈α∃testr[␈↓αd␈↓↓␈α∀u,p,f,λ:testr[␈↓αd␈↓↓
␈↓ ↓H␈↓↓u,p,f,u]]␈↓.

␈↓ ↓H␈↓The␈αobject␈αof␈αthe␈αfunction␈αis␈αto␈αfind␈αa␈αsubexpression␈αof␈α␈↓↓x␈↓␈αsatisfying␈α␈↓↓p[x]␈↓␈αand␈αreturn␈α␈↓↓f[x].␈↓␈α If␈αthe
␈↓ ↓H␈↓search␈αis␈αunsuccessful,␈αthen␈αthe␈αcontinuation␈αfunction␈α␈↓↓u[]␈↓␈αof␈αno␈αarguments␈αis␈αto␈αbe␈αcomputed␈αand
␈↓ ↓H␈↓its␈α∂value␈α⊂returned.␈α∂ The␈α∂difficulty␈α⊂was␈α∂that␈α∂when␈α⊂an␈α∂inner␈α∂recursion␈α⊂occurred,␈α∂the␈α∂value␈α⊂of␈α∂␈↓↓u␈↓
␈↓ ↓H␈↓wanted␈α
was␈α
the␈αouter␈α
value,␈α
but␈α
the␈αinner␈α
value␈α
was␈α
actually␈αused.␈α
 In␈α
modern␈αterminology,␈α
lexical
␈↓ ↓H␈↓scoping was wanted, and dynamic scoping was obtained.

␈↓ ↓H␈↓␈↓ α_I␈α
must␈α∞confess␈α
that␈α
I␈α∞regarded␈α
this␈α
difficulty␈α∞as␈α
just␈α
a␈α∞bug␈α
and␈α
expressed␈α∞confidence␈α
that
␈↓ ↓H␈↓Steve␈α
Russell␈α
would␈α
soon␈α
fix␈α∞it.␈α
 He␈α
did␈α
fix␈α
it␈α∞but␈α
by␈α
inventing␈α
the␈α
so-called␈α∞FUNARG␈α
device
␈↓ ↓H␈↓that␈α∞took␈α∞the␈α∞lexical␈α∞environment␈α∞along␈α∞with␈α∞the␈α∞functional␈α∞argument.␈α∞ Similar␈α∞difficulties␈α
later
␈↓ ↓H␈↓showed␈αup␈α
in␈αAlgol␈α60,␈α
and␈αRussell's␈αturned␈α
out␈αto␈αbe␈α
one␈αof␈αthe␈α
more␈αcomprehensive␈αsolutions␈α
to
␈↓ ↓H␈↓the problem.

␈↓ ↓H␈↓␈↓ α_e.␈α∂The␈α∂"program␈α∂feature".␈α⊂ Besides␈α∂composition␈α∂of␈α∂functions␈α∂and␈α⊂conditional␈α∂expressions,
␈↓ ↓H␈↓LISP␈αalso␈α
allows␈αsequential␈α
programs␈αwritten␈α
with␈αassignment␈α
statements␈αand␈α
␈↓αgo to␈↓s.␈α Compared
␈↓ ↓H␈↓to␈α∞the␈α
mathematically␈α∞elegant␈α∞recursive␈α
function␈α∞definition␈α∞features,␈α
the␈α∞"program␈α∞feature"␈α
looks
␈↓ ↓H␈↓like␈αa␈αhasty␈αafterthought.␈α This␈αis␈αnot␈αquite␈αcorrect;␈αthe␈αidea␈αof␈αsequential␈αprogram␈αantedates␈αthat
␈↓ ↓H␈↓of␈αrecursive␈α
function␈αdefinition.␈α However,␈α
the␈αnotation␈α
LISP␈αuses␈αfor␈α
PROGs␈αwas␈α
definitely␈αan
␈↓ ↓H␈↓afterthought and is far from optimal.

␈↓ ↓H␈↓␈↓ α_f.␈αOnce␈α
the␈α␈↓↓eval␈↓␈α
interpreter␈αwas␈α
programmed,␈αit␈α
became␈αavailable␈α
to␈αthe␈α
programmer,␈αand␈α
it
␈↓ ↓H␈↓was␈α
especially␈α
easy␈α∞to␈α
use␈α
because␈α
it␈α∞uses␈α
LISP␈α
program␈α
expressed␈α∞as␈α
LISP␈α
data.␈α∞ In␈α
particular,
␈↓ ↓H␈↓␈↓↓eval␈↓␈αmade␈αpossible␈αFEXPRS␈α
and␈αFSUBRS␈αwhich␈αare␈α"functions"␈α
that␈αare␈αnot␈αgiven␈α
their␈αactual
␈↓ ↓H␈↓arguments␈α∩but␈α∩are␈α∩given␈α⊃the␈α∩expressions␈α∩that␈α∩evaluate␈α∩to␈α⊃the␈α∩arguments␈α∩and␈α∩must␈α∩call␈α⊃␈↓↓eval␈↓
␈↓ ↓H␈↓themselves␈αwhen␈αthey␈αwant␈αthe␈αexpressions␈αevaluated.␈α The␈αmain␈αapplication␈αof␈αthis␈αfacility␈αis␈αto
␈↓ ↓H␈↓functions␈αthat␈αdon't␈αalways␈αevaluate␈αall␈αof␈αtheir␈αarguments;␈αthey␈αevaluate␈αsome␈αof␈αthem␈αfirst,␈αand
␈↓ ↓H␈↓then␈α∞decide␈α∞which␈α∞others␈α∞to␈α∞evaluate.␈α∂ This␈α∞facility␈α∞resembles␈α∞Algol's␈α∞␈↓↓call-by-name␈↓␈α∞but␈α∂is␈α∞more
␈↓ ↓H␈↓flexible, because ␈↓↓eval␈↓ is explicitly available.

␈↓ ↓H␈↓␈↓ α_g.␈αSince␈αLISP␈α
works␈αwith␈αlists,␈αit␈α
was␈αalso␈αconvenient␈αto␈α
provide␈αfor␈αfunctions␈αwith␈α
variable
␈↓ ↓H␈↓numbers␈α⊃of␈α⊃arguments␈α⊃by␈α⊃supplying␈α⊃them␈α⊃with␈α⊃a␈α⊃list␈α⊃of␈α⊃arguments␈α⊃rather␈α⊃than␈α∩the␈α⊃separate
␈↓ ↓H␈↓arguments.

␈↓ ↓H␈↓␈↓ α_Unfortunately,␈α∩none␈α∩of␈α∩the␈α∩above␈α∩features␈α∩has␈α∩been␈α∩given␈α∩a␈α∩comprehensive␈α∪and␈α∩clear
␈↓ ↓H␈↓mathematical␈α
semantics␈αin␈α
connection␈αwith␈α
LISP␈α
or␈αany␈α
other␈αprogramming␈α
language.␈α
 The␈αbest
␈↓ ↓H␈↓attempt in connection with LISP is Michael Gordon's (1973), but it is too complicated.
␈↓ ↓H␈↓␈↓ εH␈↓ 96


␈↓ ↓H␈↓␈↓ α_As␈αa␈αprogramming␈α
language␈αLISP␈αhas␈α
many␈αlimitations.␈α Some␈αof␈α
the␈αmost␈αevident␈α
in␈αthe
␈↓ ↓H␈↓early␈α1960s␈αwere␈αweak␈αnumerical␈αcomputation,␈αinability␈αto␈αrepresent␈αobjects␈αby␈αblocks␈αof␈αregisters
␈↓ ↓H␈↓and␈α
garbage␈αcollect␈α
the␈α
blocks,␈αand␈α
lack␈α
of␈αa␈α
good␈α
system␈αfor␈α
input-output␈α
of␈αsymbolic␈α
expressions
␈↓ ↓H␈↓in␈α⊗conventional␈α↔notations.␈α⊗ All␈α↔these␈α⊗problems␈α↔and␈α⊗others␈α⊗were␈α↔to␈α⊗be␈α↔fixed␈α⊗in␈α↔LISP␈α⊗2.
␈↓ ↓H␈↓Unfortunately,␈α_the␈α_LISP␈α_2␈α_project,␈α_undertaken␈α_by␈α_Information␈α_International␈α_and␈α↔System
␈↓ ↓H␈↓Development␈αCorporation␈αproved␈α
too␈αambitious␈αfor␈α
the␈αcomputer␈αthat␈α
had␈αto␈αbe␈α
used␈αand␈αfor␈α
the
␈↓ ↓H␈↓budget␈α⊃of␈α⊃the␈α∩project.␈α⊃ Therefore,␈α⊃we␈α⊃had␈α∩to␈α⊃settle␈α⊃for␈α⊃LISP␈α∩1.5␈α⊃developed␈α⊃at␈α∩M.I.T.␈α⊃which
␈↓ ↓H␈↓corrected only the most glaring deficiencies.

␈↓ ↓H␈↓␈↓ α_The␈α
existence␈α
of␈αan␈α
interpreter␈α
and␈αthe␈α
absence␈α
of␈αdeclarations␈α
makes␈α
it␈αparticularly␈α
natural
␈↓ ↓H␈↓to␈α
use␈α
LISP␈α
in␈α
a␈α
time-sharing␈α
environment.␈α It␈α
is␈α
convenient␈α
to␈α
define␈α
functions,␈α
test␈α
them,␈αand
␈↓ ↓H␈↓re-edit␈αthem␈αwithout␈αever␈αleaving␈αthe␈αLISP␈αinterpreter.␈α A␈αdemonstration␈αof␈αLISP␈αin␈αa␈αprototype
␈↓ ↓H␈↓time-sharing␈α
environment␈α
on␈αthe␈α
IBM␈α
704␈α
was␈αmade␈α
in␈α
xxx␈α
1960␈α(or␈α
1961?).␈α
 L.␈α
Peter␈αDeutsch
␈↓ ↓H␈↓implemented␈αthe␈αfirst␈αinteractive␈αLISP␈αon␈αthe␈α
PDP-1␈αcomputer␈αin␈α1962?,␈αbut␈αthe␈αPDP-1␈αwas␈α
had
␈↓ ↓H␈↓too small a memory for serious symbolic computation.

␈↓ ↓H␈↓␈↓ α_The␈αmost␈αimportant␈αimplementations␈αof␈αLISP␈αproved␈αto␈αbe␈αthose␈αfor␈αthe␈αPDP-6␈αcomputer
␈↓ ↓H␈↓and␈α⊗its␈α⊗successor␈α⊗the␈α∃PDP-10␈α⊗made␈α⊗by␈α⊗the␈α∃Digital␈α⊗Equipment␈α⊗Corporation␈α⊗of␈α∃Maynard,
␈↓ ↓H␈↓Massachusetts.␈α∞ In␈α∂fact,␈α∞the␈α∂half␈α∞word␈α∂instructions␈α∞and␈α∂the␈α∞stack␈α∂instructions␈α∞of␈α∂these␈α∞machines
␈↓ ↓H␈↓were␈αdeveloped␈αwith␈αLISP's␈αrequirements␈αin␈αmind.␈α The␈αearly␈αdevelopment␈αof␈αLISP␈αat␈αM.I.T.␈αfor
␈↓ ↓H␈↓this␈α⊃line␈α⊂of␈α⊃machines␈α⊂and␈α⊃its␈α⊂subsequent␈α⊃development␈α⊂of␈α⊃BBN␈α⊂LISP␈α⊃(aka␈α⊃INTERLISP)␈α⊂and
␈↓ ↓H␈↓MACLISP␈α∪also␈α∪contributed␈α∪to␈α∪making␈α∪these␈α∪machines␈α∪the␈α∪machines␈α∪of␈α∪choice␈α∪for␈α∩artificial
␈↓ ↓H␈↓intelligence␈αresearch.␈α The␈αIBM␈α704␈αLISP␈αwas␈αextended␈αto␈αthe␈αIBM␈α7090␈αand␈αlater␈αled␈αto␈αLISPs
␈↓ ↓H␈↓for the IBM 360 and 370.

␈↓ ↓H␈↓␈↓ α_The␈α∂earliest␈α∂publications␈α∂on␈α∂LISP␈α∂were␈α∂in␈α∂the␈α∂Quarterly␈α∂Progress␈α∂Reports␈α∂of␈α∂the␈α∂M.I.T.
␈↓ ↓H␈↓Research␈α⊃Laboratory␈α⊂of␈α⊃Electronics.␈α⊂ (McCarthy␈α⊃1960)␈α⊂was␈α⊃the␈α⊂first␈α⊃journal␈α⊃publication.␈α⊂ The
␈↓ ↓H␈↓␈↓↓LISP␈αProgrammer's␈α
Manual␈↓␈αby␈αPhyllis␈α
Fox␈αwas␈α
published␈αby␈αthe␈α
Research␈αLaboratory␈α
in␈α196x
␈↓ ↓H␈↓and␈αthe␈α␈↓↓LISP␈α1.5␈αProgrammer's␈αManual␈↓␈αby␈αMcCarthy,␈αLevin,␈αet.␈αal.␈α in␈α196x␈αwas␈α
published␈αby
␈↓ ↓H␈↓M.I.T.␈αPress.␈α After␈αthe␈αpublication␈α
of␈α(McCarthy␈αand␈αLevin␈α196x),␈αmany␈α
LISP␈αimplementations
␈↓ ↓H␈↓were␈α∞made␈α∂for␈α∞numerous␈α∞computers.␈α∂ However,␈α∞in␈α∂contrast␈α∞the␈α∞situation␈α∂with␈α∞most␈α∂widely␈α∞used
␈↓ ↓H␈↓programming␈α∞languages,␈α∞no␈α∂organization␈α∞has␈α∞ever␈α∞attempted␈α∂to␈α∞propagate␈α∞LISP,␈α∞and␈α∂there␈α∞has
␈↓ ↓H␈↓never been an attempt at standardization.

␈↓ ↓H␈↓4. Conclusions.

␈↓ ↓H␈↓␈↓ α_LISP␈α∀is␈α∪now␈α∀the␈α∀second␈α∪oldest␈α∀programming␈α∀language␈α∪(after␈α∀FORTRAN)␈α∀in␈α∪present
␈↓ ↓H␈↓widespread␈αuse.␈α It␈α
owes␈αits␈αlongevity␈α
to␈αthe␈αfact␈αthat␈α
its␈αcore␈αoccupies␈α
some␈αkind␈αof␈αlocal␈α
optimum
␈↓ ↓H␈↓in␈α∂the␈α∂space␈α∂of␈α∂programming␈α∂languages␈α∂given␈α∂that␈α∂static␈α∂friction␈α∂discourages␈α⊂purely␈α∂notational
␈↓ ↓H␈↓changes.␈α↔ Recursive␈α↔use␈α⊗of␈α↔conditional␈α↔expressions,␈α⊗representation␈α↔of␈α↔symbolic␈α⊗information
␈↓ ↓H␈↓externally␈αby␈αlists␈αand␈αinternally␈αby␈αlist␈αstructure,␈αand␈αrepresentation␈αof␈αprogram␈αin␈αthe␈αsame␈αway
␈↓ ↓H␈↓will␈α∂probably␈α∂have␈α∂a␈α∂very␈α∂long␈α∂life.␈α∂ LISP␈α∂itself␈α∂will␈α∂probably␈α∂become␈α∂obsolete␈α⊂when␈α∂someone
␈↓ ↓H␈↓succeeds␈α⊂in␈α⊂making␈α⊂a␈α∂more␈α⊂comprehensive␈α⊂language␈α⊂that␈α∂dominates␈α⊂LISP␈α⊂practically␈α⊂and␈α∂also
␈↓ ↓H␈↓gives a clear mathematical semantics to a more comprehensive set of features.

␈↓ ↓H␈↓5. References.
␈↓ ↓H␈↓␈↓ εH␈↓ 97


␈↓ ↓H␈↓APPENDIX I - A MICRO-MANUAL FOR LISP - NOT THE WHOLE TRUTH

␈↓ ↓H␈↓␈↓ α_LISP␈α
data␈αare␈α
symbolic␈α
expressions␈αthat␈α
can␈αbe␈α
either␈α
␈↓↓atoms␈↓␈αor␈α
␈↓↓lists␈↓.␈α ␈↓↓Atoms␈↓␈α
are␈α
strings␈αof
␈↓ ↓H␈↓letters␈α⊃and␈α⊃digits␈α⊃and␈α⊃other␈α⊃characters␈α⊃not␈α⊃otherwise␈α⊃used␈α⊃in␈α⊃LISP.␈α⊃ A␈α⊃list␈α⊃consists␈α⊃of␈α∩a␈α⊃left
␈↓ ↓H␈↓parenthesis␈αfollowed␈α
by␈αzero␈α
or␈αmore␈α
atoms␈αor␈αlists␈α
separated␈αby␈α
spaces␈αand␈α
ending␈αwith␈α
a␈αright
␈↓ ↓H␈↓parenthesis.␈α
 Examples:␈α∞A,␈α
ONION,␈α
(),␈α∞(A),␈α
(A␈α
ONION␈α∞A),␈α
(PLUS␈α
3␈α∞(TIMES␈α
X␈α
PI)␈α∞1),␈α
(CAR
␈↓ ↓H␈↓(QUOTE (A B))).

␈↓ ↓H␈↓␈↓ α_The␈α∂LISP␈α⊂programming␈α∂language␈α⊂is␈α∂defined␈α⊂by␈α∂rules␈α⊂whereby␈α∂certain␈α⊂LISP␈α∂expressions
␈↓ ↓H␈↓have␈α∞other␈α∂LISP␈α∞expressions␈α∂as␈α∞␈↓↓values␈↓.␈α∞ The␈α∂function␈α∞called␈α∂␈↓↓value␈↓␈α∞that␈α∞we␈α∂use␈α∞in␈α∂giving␈α∞these
␈↓ ↓H␈↓rules␈α
is␈α
not␈α
part␈α
of␈α
the␈α
LISP␈α
language␈α
but␈α
rather␈α
part␈α
of␈α
the␈α
informal␈α
mathematical␈α
language␈α
used
␈↓ ↓H␈↓to␈α⊃define␈α⊃LISP.␈α⊃ Likewise,␈α⊃the␈α⊃italic␈α⊃letters␈α⊃␈↓↓e␈↓␈α⊃and␈α⊃␈↓↓a␈↓␈α⊃(sometimes␈α⊃with␈α⊃subscripts)␈α∩denote␈α⊃LISP
␈↓ ↓H␈↓expressions,␈αthe␈αletter␈α␈↓↓v␈↓␈α(usually␈αsubscripted)␈αdenotes␈αan␈αatom␈αserving␈αas␈αa␈αvariable,␈αand␈αthe␈αletter
␈↓ ↓H␈↓␈↓↓f␈↓ stands for a LISP expression serving as a function name.

␈↓ ↓H␈↓1. ␈↓↓value␈↓ (QUOTE ␈↓↓e)␈↓ = e.  Thus the value of (QUOTE A) is A.

␈↓ ↓H␈↓2.␈α⊃␈↓↓value␈↓␈α⊃(CAR␈α⊃␈↓↓e),␈↓␈α⊃where␈α⊃␈↓↓value␈α⊃e␈↓␈α⊃is␈α⊂a␈α⊃non-empty␈α⊃list,␈α⊃is␈α⊃the␈α⊃first␈α⊃element␈α⊃of␈α⊃␈↓↓value e.␈↓␈α⊂ Thus
␈↓ ↓H␈↓␈↓↓value␈↓ (CAR (QUOTE (A B C))) = A.

␈↓ ↓H␈↓3.␈α∞␈↓↓value␈↓␈α∞(CDR␈α∞e),␈α∞where␈α∞␈↓↓value␈↓␈α∞␈↓↓e␈↓␈α∞is␈α∞a␈α
non-empty␈α∞list,␈α∞is␈α∞the␈α∞the␈α∞list␈α∞that␈α∞remains␈α∞when␈α∞the␈α
first
␈↓ ↓H␈↓element of ␈↓↓value e␈↓ is deleted.  Thus ␈↓↓value␈↓ (CDR (QUOTE (A B C))) = (B C).

␈↓ ↓H␈↓4.␈α
␈↓↓value␈↓␈α
(CONS␈α
␈↓↓e1␈↓␈α
␈↓↓e2),␈↓␈α
is␈α
the␈α
list␈α
that␈α
results␈α
from␈α
prefixing␈α
␈↓↓value e1␈↓␈α
onto␈α
the␈α
list␈α
␈↓↓value e2.␈↓␈α
 Thus
␈↓ ↓H␈↓␈↓↓value␈↓ (CONS (QUOTE A) (QUOTE (B C))) = (A B C).

␈↓ ↓H␈↓5.␈α∩␈↓↓value␈↓␈α∩(EQUAL␈α∩␈↓↓e1␈↓␈α⊃␈↓↓e2)␈↓␈α∩is␈α∩T␈α∩if␈α∩␈↓↓value␈↓␈α⊃␈↓↓e1␈↓␈α∩=␈α∩␈↓↓value␈↓␈α∩␈↓↓e2.␈↓␈α⊃ Otherwise,␈α∩its␈α∩value␈α∩is␈α∩NIL.␈α⊃ Thus
␈↓ ↓H␈↓␈↓↓value␈↓ (EQUAL (CAR (QUOTE (A B))) (QUOTE A)) = T.

␈↓ ↓H␈↓6. ␈↓↓value␈↓ (ATOM ␈↓↓e)␈↓ = T if ␈↓↓value␈↓ ␈↓↓e␈↓ is an atom; otherwise its value is NIL.

␈↓ ↓H␈↓7.␈α
␈↓↓value␈↓␈α(COND(␈↓↓p␈↓β1␈↓↓␈α
e␈↓β1␈↓↓)␈α
...␈α(p␈↓βn␈↓↓␈α
e␈↓βn␈↓↓))␈α
=␈αvalue␈α
e␈↓βi␈↓,␈αwhere␈α
␈↓↓p␈↓βi␈↓␈α
is␈αthe␈α
the␈α
first␈αof␈α
the␈α
␈↓↓p␈↓'s␈αwhose␈α
value␈αis␈α
not
␈↓ ↓H␈↓NIL.  Thus

␈↓ ↓H␈↓␈↓↓value␈↓ (COND ((ATOM (QUOTE A)) (QUOTE B)) ((QUOTE T) (QUOTE C))) = B.

␈↓ ↓H␈↓8. An atom ␈↓↓v,␈↓ regarded as a variable, may have a value.

␈↓ ↓H␈↓9.␈α
␈↓↓value␈↓␈α
((LAMBDA␈α
(␈↓↓v␈↓β1␈↓↓␈α
...␈α
v␈↓βn␈↓↓)␈α
e)␈α
e␈↓β1␈↓↓␈α
...␈α
e␈↓βn␈↓↓)␈↓␈α
is␈α
the␈α
same␈α
as␈α
␈↓↓value e␈↓␈α
but␈α
in␈α
an␈α
environment␈α
in␈α
which
␈↓ ↓H␈↓the␈α∞variables␈α∞␈↓↓v␈↓β1␈↓↓ ... v␈↓βn␈↓↓␈↓␈α∞take␈α∞the␈α∞values␈α∂of␈α∞the␈α∞expressions␈α∞␈↓↓e␈↓β1␈↓↓ ... e␈↓βn␈↓↓␈↓␈α∞in␈α∞the␈α∂original␈α∞environment.
␈↓ ↓H␈↓Thus

␈↓ ↓H␈↓␈↓↓value␈↓␈α((LAMBDA␈L(X␈α
Y)␈α(CONS␈α(CAR␈α
X)␈αY))␈α(QUOTE␈α
(A␈αB))␈α(CDR␈α
(QUOTE␈α(C␈αD))))␈α
=␈α(A
␈↓ ↓H␈↓D).

␈↓ ↓H␈↓10.␈α∞Here's␈α∞the␈α∞hard␈α∞one.␈α∞ ␈↓↓value␈↓␈α
((LABEL␈α∞␈↓↓f␈↓␈α∞(LAMBDA␈α∞␈↓↓(v␈↓β1␈↓↓␈α∞...␈α∞v␈↓βn␈↓↓)␈α
e))␈α∞e␈↓β1␈↓↓␈α∞...␈α∞e␈↓βn␈↓↓)␈↓␈α∞is␈α∞the␈α∞same␈α
as
␈↓ ↓H␈↓␈↓↓value␈↓␈α
((LAMBDA␈α
(␈↓↓v␈↓β1␈↓↓␈α
...␈α
v␈↓βn␈↓↓)␈α
e)␈α
e␈↓β1␈↓↓␈α
...␈α
e␈↓βn␈↓↓)␈↓␈α
with␈α
the␈α
additional␈α
rule␈α
that␈α
whenever␈α
␈↓↓(f a␈↓β1␈↓↓ ... a␈↓βn␈↓↓)␈↓␈α
must
␈↓ ↓H␈↓be␈α
evaluated,␈α␈↓↓f␈↓␈α
is␈αreplaced␈α
by␈α(LABEL ␈↓↓f␈↓ (LAMBDA (␈↓↓v␈↓β1␈↓↓ ... v␈↓βn␈↓↓)␈α
e))␈↓.␈α Lists␈α
beginning␈αwith␈α
LABEL
␈↓ ↓H␈↓define functions recursively.
␈↓ ↓H␈↓␈↓ εH␈↓ 98


␈↓ ↓H␈↓␈↓ α_This is the core of LISP, and here are more examples:

␈↓ ↓H␈↓␈↓↓value␈↓␈α(CAR␈αX)␈α=␈α(A␈αB)␈αif␈α␈↓↓value␈↓␈αX␈α=␈α((A␈αB)␈αC),␈αand␈α␈↓↓value␈↓␈α((LABEL␈αFF␈α(LAMBDA␈α(X)␈α(COND
␈↓ ↓H␈↓((ATOM␈αX)␈αX)␈α((QUOTE␈αT)␈α(FF␈α(CAR␈αX))))))␈α(QUOTE␈α((A␈αB)␈αC)))␈α=␈αA.␈α Thus␈α((LABEL␈αFF
␈↓ ↓H␈↓(LAMBDA␈α(X)␈α(COND␈α((ATOM␈αX)␈αX)␈α((QUOTE␈αT)␈α(FF␈α(CAR␈αX)))))),␈αis␈αthe␈αLISP␈αname␈αof␈αa
␈↓ ↓H␈↓function␈α⊂␈↓↓ff␈↓␈α⊂such␈α⊂that␈α⊂␈↓↓ff e␈↓␈α⊂is␈α∂the␈α⊂first␈α⊂atom␈α⊂in␈α⊂the␈α⊂written␈α⊂form␈α∂of␈α⊂␈↓↓e.␈↓␈α⊂Note␈α⊂that␈α⊂the␈α⊂list␈α⊂␈↓↓ff␈↓␈α∂is
␈↓ ↓H␈↓substituted for the atom FF twice.

␈↓ ↓H␈↓Difficult mathematical type exercise: Find a list e such that ␈↓↓value e = e.␈↓

␈↓ ↓H␈↓␈↓αAbbreviations␈↓

␈↓ ↓H␈↓␈↓ α_The above LISP needs some abbreviations for practical use.

␈↓ ↓H␈↓1.␈α∞The␈α∞variables␈α∞T␈α∞and␈α∞NIL␈α∞are␈α∞permanently␈α
assigned␈α∞the␈α∞values␈α∞T␈α∞and␈α∞NIL,␈α∞and␈α∞NIL␈α∞is␈α
the
␈↓ ↓H␈↓name of the null list ().

␈↓ ↓H␈↓2.␈αSo␈αas␈αnot␈αto␈αdescribe␈αa␈αLISP␈αfunction␈αeach␈αtime␈αit␈αis␈αused,␈αwe␈αdefine␈αit␈αpermanently␈αby␈αtyping
␈↓ ↓H␈↓(DEFUN␈α␈↓↓f␈α(v␈↓β1␈↓↓␈α...␈αv␈↓βn␈↓↓)␈αe)␈↓.␈α Thereafter␈α␈↓↓(f␈αe␈↓β1␈↓↓␈α...␈αe␈↓βn␈↓↓)␈↓␈αis␈αevaluated␈αby␈αevaluating␈α␈↓↓e␈↓␈αwith␈αthe␈αvariables
␈↓ ↓H␈↓␈↓↓v␈↓β1␈↓↓, ... ,v␈↓βn␈↓↓␈↓␈αtaking␈αthe␈α
values␈α␈↓↓value e␈↓β1␈↓↓, ... ,value e␈↓βn␈↓↓␈↓␈αrespectively.␈α
 Thus,␈αafter␈αwe␈αdefine␈α
(DEFUN
␈↓ ↓H␈↓FF␈α
(X)␈α
(COND␈α((ATOM␈α
X)␈α
X)␈α(T␈α
(FF␈α
(CAR␈α
X))))),␈αtyping␈α
 (FF␈α
(QUOTE␈α((A␈α
B)␈α
C))),␈α
gets␈αA
␈↓ ↓H␈↓from LISP.

␈↓ ↓H␈↓3. We have the permanent function definitions

␈↓ ↓H␈↓(DEFUN NULL (X) (EQUAL X NIL)) and

␈↓ ↓H␈↓(DEFUN CADR (X) (CAR (CDR X))),

␈↓ ↓H␈↓and similarly for arbitrary combinations of A and D.

␈↓ ↓H␈↓4. (LIST ␈↓↓e␈↓β1␈↓↓ ... e␈↓βn␈↓↓␈↓) is defined for each ␈↓↓n␈↓ to be (CONS ␈↓↓e␈↓␈↓β1␈↓ (CONS ... (CONS ␈↓↓e␈↓␈↓βn␈↓ NIL))).

␈↓ ↓H␈↓5.␈α(AND␈α␈↓↓p␈↓␈α␈↓↓q)␈↓␈αabbreviates␈α(COND␈α(␈↓↓p␈↓␈α␈↓↓q)␈↓␈α(T␈αNIL)).␈α ANDs␈αwith␈αmore␈αterms␈αare␈αdefined␈αsimilarly,
␈↓ ↓H␈↓and␈α∃the␈α⊗propositional␈α∃connectives␈α⊗OR␈α∃and␈α⊗NOT␈α∃are␈α⊗used␈α∃in␈α⊗abbreviating␈α∃corresponding
␈↓ ↓H␈↓conditional expressions.

␈↓ ↓H␈↓␈↓ α_Here are more examples of LISP function definitions:

␈↓ ↓H␈↓(DEFUN␈αALT␈α(X)␈α(COND␈α((OR␈α(NULL␈αX)␈α(NULL␈α(CDR␈αX)))␈αX)␈α(T␈α(CONS␈α(CAR␈αX)␈α(ALT
␈↓ ↓H␈↓(CDDR X))))))

␈↓ ↓H␈↓defines␈α∂a␈α∂function␈α∂that␈α∂gives␈α∂alternate␈α∂elements␈α∂of␈α∂a␈α∂list␈α∂starting␈α∂with␈α∂the␈α∂first␈α⊂element.␈α∂ Thus
␈↓ ↓H␈↓(ALT (QUOTE (A B C D E))) = (A C E).

␈↓ ↓H␈↓(DEFUN␈α
SUBST␈α(X␈α
Y␈αZ)␈α
(COND␈α((ATOM␈α
Z)␈α(COND␈α
((EQUAL␈αZ␈α
Y)␈αX)␈α
(T␈αZ)))␈α
(T␈α(CONS
␈↓ ↓H␈↓(SUBST X Y (CAR Z)) (SUBST X Y (CDR Z)))))),

␈↓ ↓H␈↓where Y is an atom, gives the result of substituting X for Y in Z.  Thus
␈↓ ↓H␈↓␈↓ εH␈↓ 99


␈↓ ↓H␈↓(SUBST␈α(QUOTE␈α(PLUS␈α
X␈αY))␈α(QUOTE␈α
V)␈α(QUOTE␈α(TIMES␈αX␈α
V)))␈α=␈α(TIMES␈α
X␈α(PLUS
␈↓ ↓H␈↓X Y)).

␈↓ ↓H␈↓␈↓ α_You␈α⊃may␈α⊃now␈α⊃program␈α⊂in␈α⊃LISP.␈α⊃ Call␈α⊃LISP␈α⊂on␈α⊃a␈α⊃time-sharing␈α⊃computer,␈α⊃define␈α⊂some
␈↓ ↓H␈↓functions, type in a LISP expression, and LISP will output its value on your terminal.

␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓ARPANET: MCCARTHY@SU-AI

␈↓ ↓H␈↓␈↓εThis draft of LISP[F77,JMC] PUBbed at 16:07 on November 13, 1977.␈↓
␈↓ ↓H␈↓␈↓ εH␈↓ *10


␈↓ ↓H␈↓***In␈αgeneral␈αI␈αthink␈αthat␈αthe␈αpaper␈α
is␈αa␈αgood␈αstart.␈α However,␈αthe␈αintroductory␈αparagraph␈α
might
␈↓ ↓H␈↓better␈αserve␈αas␈αa␈α
conclusion␈αafter␈αto␈αyou␈αhave␈α
introduced␈αand␈αexplained␈αthe␈αconcepts␈α
involved***
␈↓ ↓H␈↓[I compromised - making it the second paragraph].

␈↓ ↓H␈↓***The␈α⊃following␈α⊃paragraph␈α∩might␈α⊃be␈α⊃a␈α∩good␈α⊃place␈α⊃to␈α∩start␈α⊃the␈α⊃paper***␈α∩[This␈α⊃suggestion
␈↓ ↓H␈↓adopted].

␈↓ ↓H␈↓***Perhaps␈α~"subexpressions"␈α→is␈α~better␈α→than␈α~"subsubexpressions"***fixed␈α~[This␈α→suggestion
␈↓ ↓H␈↓adopted].

␈↓ ↓H␈↓***You␈α∪might␈α∪want␈α∪to␈α∪mention␈α∪the␈α∀Advice␈α∪Taker␈α∪Project␈α∪at␈α∪some␈α∪point␈α∪and␈α∀explain␈α∪the
␈↓ ↓H␈↓relationship of the development of LISP to furthering the goals of that project*** [done]

␈↓ ↓H␈↓***In␈αan␈αappendix␈αit␈αmight␈αbe␈αworthwhile␈α
to␈αpresent␈αthe␈αdefinition␈αof␈αEVAL␈αtogether␈α
with␈αthe
␈↓ ↓H␈↓modification␈α
that␈αmakes␈α
upward␈αfunargs␈α
work.***␈αCarl:␈α
Can␈αyou␈α
supply␈αme␈α
with␈αsuch␈α
an␈αeval?
␈↓ ↓H␈↓[I will include the micro-manual as an appendix].

␈↓ ↓H␈↓***The␈α
following␈αcomment␈α
about␈α
the␈αdenotational␈α
semantics␈α
of␈αRPLACA␈α
and␈α
RPLACD␈αseems
␈↓ ↓H␈↓out␈α⊂of␈α⊂place␈α⊂in␈α⊃the␈α⊂early␈α⊂history␈α⊂of␈α⊂LISP***␈α⊃[dropped␈α⊂from␈α⊂this␈α⊂place␈α⊂but␈α⊃partially␈α⊂restored
␈↓ ↓H␈↓further on].

␈↓ ↓H␈↓Semantically,␈α⊂they␈α⊂must␈α⊂be␈α⊂represented␈α⊂by␈α∂functions␈α⊂of␈α⊂state,␈α⊂and␈α⊂only␈α⊂Michael␈α⊂Gordon␈α∂really
␈↓ ↓H␈↓understands␈α∞them.␈α
 All␈α∞this␈α
could␈α∞not␈α
be␈α∞formulated␈α
precisely␈α∞while␈α
LISP␈α∞was␈α∞being␈α
developed,
␈↓ ↓H␈↓but it was clear that ␈↓↓rplaca␈↓ and ␈↓↓rplacd␈↓ were anomalous.

␈↓ ↓H␈↓***Where did FEXPRS come from?*** [answered].

␈↓ ↓H␈↓***How␈α
did␈α
PROG␈α
get␈α
introduced␈α
into␈α
LISP?␈α Was␈α
its␈α
introduction␈α
merely␈α
a␈α
concession␈α
to␈αthe
␈↓ ↓H␈↓FORTRAN␈α
mentality.␈α
 At␈α
this␈α
time␈α
you␈α
already␈αknew␈α
how␈α
to␈α
translate␈α
programs␈α
that␈α
use␈αgotos
␈↓ ↓H␈↓into␈αrecursive␈αfunction␈αcalls.␈α The␈αresulting␈αfunctions␈αare␈αtail␈αrecursive␈αso␈αthey␈αdo␈αnot␈αneed␈αto␈αuse
␈↓ ↓H␈↓up␈αany␈αstorage␈αon␈αthe␈αpushdown␈αstack␈αeither␈αinterpreted␈αor␈αcompiled␈α(see␈αmy␈αrecent␈αpaper␈αin␈αthe
␈↓ ↓H␈↓A.I. Journal on "Viewing Control Structures as Patterns of Passing Messages")*** [answered].

␈↓ ↓H␈↓***You␈α
might␈α∞also␈α
want␈α
to␈α∞mention␈α
the␈α
pdp-1␈α∞LISP␈α
system␈α
developed␈α∞by␈α
Peter␈α∞Deutsch.␈α
 Was
␈↓ ↓H␈↓the PDP-1 system the first LISP system to be used interactively?*** [Don't know.].

␈↓ ↓H␈↓***Contemporaneous␈α∪with␈α∩the␈α∪development␈α∩of␈α∪the␈α∪LISP␈α∩2␈α∪project␈α∩was␈α∪the␈α∪development␈α∩of
␈↓ ↓H␈↓MACLISP␈αon␈αthe␈αPDP-6.␈α  In␈αfact␈αAlan␈αKotok␈αexplicitly␈αput␈αthe␈αhalf␈αword␈αinstructions␈αinto␈αthe
␈↓ ↓H␈↓PDP-6␈αorder␈αcode␈αpartly␈αas␈αa␈αresult␈αof␈αseeing␈αhow␈αuseful␈αthey␈αwould␈αbe␈αin␈αthe␈αimplementation␈αof
␈↓ ↓H␈↓LISP**** [PDP-6 and its role in LISP discussed].

␈↓ ↓H␈↓***Why was the function LABEL was included in LISP?*** [answered].

␈↓ ↓H␈↓***Why␈αwere␈αRPLACA␈αand␈αRPLACD␈αconsidered␈αto␈αbe␈αmore␈αanomalous␈αthan␈αPUTPROP␈αand
␈↓ ↓H␈↓GETPROP?*** [I don't want to discuss the property list functions].

␈↓ ↓H␈↓***The␈αfollowing␈αparagraph␈αmakes␈αa␈αgood␈αpoint␈αthat␈αcould␈αbe␈αbacked␈αup␈αwith␈αspecific␈αexamples
␈↓ ↓H␈↓if the paragraph were placed later in the paper*** [This point not specifically responded to].
␈↓ ↓H␈↓␈↓ εH␈↓ *11


␈↓ ↓H␈↓***The␈α
next␈α
paragraph␈α
seems␈α
a␈α
bit␈α
disjointed.␈α
 Many␈α
topics␈α
have␈α
been␈α
superficially␈α
mentioned␈α
so
␈↓ ↓H␈↓far.␈α∞ Perhaps␈α
a␈α∞better␈α∞approach␈α
is␈α∞to␈α
cover␈α∞the␈α∞topics␈α
in␈α∞historical␈α
order␈α∞as␈α∞you␈α
do␈α∞later␈α∞in␈α
the
␈↓ ↓H␈↓paper*** [I made it the second paragraph].

␈↓ ↓H␈↓␈↓ α_In␈α
addition␈αto␈α
its␈αcore␈α
consisting␈α
of␈αrecursive␈α
conditional␈αexpression␈α
and␈αBoolean␈α
expression
␈↓ ↓H␈↓definitions␈α∞built␈α∞up␈α∞from␈α∞the␈α∞three␈α∞functions␈α∞␈↓↓car␈↓,␈α∞␈↓↓cdr␈↓␈α∞and␈α∞␈↓↓cons␈↓␈α∞and␈α∞the␈α∞predicates␈α∞␈↓↓atom␈↓␈α∞and␈α∞␈↓↓eq␈↓,
␈↓ ↓H␈↓LISP␈αhas␈αmany␈αfeatures␈αadopted␈αfrom␈αother␈αprogramming␈αlanguages␈αof␈αthe␈αlate␈αfifties␈α
and␈αearly
␈↓ ↓H␈↓sixties.␈α
 A␈α∞recurrent␈α
issue␈α
has␈α∞always␈α
been␈α
how␈α∞to␈α
handle␈α
free␈α∞variables␈α
in␈α∞function␈α
definitions.
␈↓ ↓H␈↓This␈α
problem␈α
has␈αalso␈α
plagued␈α
Algol␈αand␈α
other␈α
programming␈αlanguages,␈α
and␈α
a␈α
compromise␈αhas
␈↓ ↓H␈↓always␈αbeen␈αnecessary␈αbetween␈αdefinitional␈αpower␈αand␈αhigh␈αspeed␈αimplementation␈αby␈αinterpreters
␈↓ ↓H␈↓and compilers.  [omitted as suggested].

␈↓ ↓H␈↓***The␈α∩compatibility␈α∪between␈α∩the␈α∩LISP␈α∪compiler␈α∩and␈α∪interpreter␈α∩has␈α∩been␈α∪one␈α∩of␈α∪its␈α∩most
␈↓ ↓H␈↓important␈α∀innnovations.␈α∀ This␈α∀allows␈α∀the␈α∀convenience␈α∀of␈α∀interactive␈α∀editing␈α∃and␈α∀debugging
␈↓ ↓H␈↓afforded␈αby␈αinterpreters␈αwhile␈αpreserving␈αthe␈αefficiency␈αthat␈αcan␈αbe␈αobtained␈αfrom␈αcompiled␈αcode.
␈↓ ↓H␈↓However,␈α
the␈α∞LISP␈α
interpreter␈α
and␈α∞compiler␈α
were␈α
nor␈α∞perfectly␈α
compatible.␈α
 You␈α∞might␈α
usefully
␈↓ ↓H␈↓discuss␈α∞SPECIAL␈α∂and␈α∞COMMON␈α∞variables.***␈α∂[Tentatively,␈α∞I␈α∞have␈α∂decided␈α∞not␈α∞to␈α∂raise␈α∞this
␈↓ ↓H␈↓issue; you might raise it in commentary if you want].